package com.lwt.codetop.dp;

// 53. 最大子数组和

/**
 * 找出连续的最大的子数组和：两种解法
 * 思路一：dp: f[i]: 表示以nums[i]结尾的最大子数组和为f[i]
 *           状态转移：f[i] = max(nums[i], nums[i] + f[i - 1])
 *           答案更新：res = Math.max(res, f[i]
 *           初始化：f[0] = nums[0]
 * 思路2：贪心 + 前缀和 + 前后缀最值预处理
 */
public class MaximumSubarraySum {

    public static void main(String[] args) {
        // 构建测试用例
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int res = maxSubArray(nums);
        System.out.println(res);
    }

    /**
     * 思路一：dp
     * @param nums
     * @return
     */
    private static int maxSubArray(int[] nums) {
        int res = nums[0];
        int n = nums.length;
        int[] f = new int[n + 10];
        f[0] = nums[0];
        for(int i = 1; i < n; i ++){
            f[i] = Math.max(nums[i], nums[i] + f[i  - 1]);
            res = Math.max(res, f[i]);
        }
        return res;
    }
    /**
     * 思路2：贪心 + 前缀和 + 前后缀最值预处理
     * @param nums
     * @return
     */
}
